/*
 * @lc app=leetcode.cn id=1568 lang=cpp
 *
 * [1568] 使陆地分离的最少天数
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int minDays(vector<vector<int>>& grid) {
        rowNum = grid.size();
        colNum = grid[0].size();
        // -1 never visited
        // 0  visited, no neighbor or dfs recurrsion not finished
        // n  neighbor num
        firstVisitedTime_.resize(rowNum, vector<int>(colNum, -1));

        int clusterCounter = 0;

        for (int i=0;i<rowNum;i++){
            for (int j=0;j<colNum;j++){
                if (grid[i][j] == 1 and firstVisitedTime_[i][j] == -1){
                    clusterCounter++;
                    dfs(i, j, grid);
                }
            }
        }

        if (clusterCounter == 0){return 0;}
        if (clusterCounter > 1){return 0;}
        ;
        // plotMatrix(grid);
        // plotMatrix(firstVisitedTime_);

        // have already known the neighbor num of every cell

        // do :
        // set the cell which has most neighbors
        // and let its neighbor's neighbor num -1 
        // untill :
        // each cell has no neighbors

        // count loop times

        bool finish = false;
        while (!finish){
            finish = finishTransferContinent();
            // plotMatrix(grid);
            // plotMatrix(firstVisitedTime_);
        }

        // if only one island, kill it
        int islandNum = 0;
        for (int row=0;row<rowNum;row++){
            for (int col=0;col<colNum;col++){
                // search island
                if (firstVisitedTime_[row][col] == 0){
                    islandNum ++;
                }
            }
        }
        if (islandNum == 1){transferCounter_ += 1;}
        return transferCounter_;
    }
private:
    int transferCounter_ = 0;
    bool finishTransferContinent(){
        int maxEdgeNum = 0;
        int transferRow;
        int transferCol;
        for (int row=0;row<rowNum;row++){
            for (int col=0;col<colNum;col++){
                // 4 neibors ~
                if (firstVisitedTime_[row][col] == 4){
                    transferContinent(row, col);
                    return false;
                }
                // search max
                if (firstVisitedTime_[row][col] > maxEdgeNum){
                    transferRow = row;
                    transferCol = col;
                    maxEdgeNum = firstVisitedTime_[row][col];
                }
            }
        }
        if (maxEdgeNum > 0){
            transferContinent(transferRow, transferCol);
            return false;
        }
        return true;
    }
    void transferContinent(int row, int col){
        transferCounter_ += 1;

        firstVisitedTime_[row][col] = -1;
        for (int i=0;i<4;i++){
            int neighborRow = row + neighborDirection[i][0];
            int neighborCol = col + neighborDirection[i][1];
            if (neighborRow<0 or neighborRow>=rowNum){continue;}
            if (neighborCol<0 or neighborCol>=colNum){continue;}
            if (firstVisitedTime_[neighborRow][neighborCol] == -1){
                continue;
            }

            // this neighbor's neighbor num -= 1
            firstVisitedTime_[neighborRow][neighborCol] -= 1;
        }
    }

    int rowNum;
    int colNum;

    vector<vector<int>> firstVisitedTime_;
    vector<vector<int>> minVisitedTime_circleId_;

    void dfs(int row, int col, vector<vector<int>>& grid){
        int edgeNum = 0;
        firstVisitedTime_[row][col] = 0;
        for (int i=0;i<4;i++){
            int neighborRow = row + neighborDirection[i][0];
            int neighborCol = col + neighborDirection[i][1];
            if (validNeighbor(neighborRow, neighborCol, grid)){
                edgeNum ++;
                // not visited
                if (firstVisitedTime_[neighborRow][neighborCol] == -1){
                    firstVisitedTime_[neighborRow][neighborCol] = 0;
                    dfs(neighborRow, neighborCol, grid);
                }
            }
        }
        firstVisitedTime_[row][col] = edgeNum;
    }
    inline bool validNeighbor(int row, int col, vector<vector<int>>& grid){
        // inside map
        if (row<0 or row>=rowNum){return false;}
        if (col<0 or col>=colNum){return false;}
        // is island
        if (grid[row][col] != 1){return false;}
        // // not visited
        // if (firstVisitedTime_[row][col] != -1){return false;}
        return true;
    }
    const int neighborDirection[4][2] = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };

    // void plotMatrix(vector<vector<int>>& res){
    //     printf("---------\n");
    //     for (int i=0;i<res.size();i++){
    //         for (int j=0;j<res[0].size();j++){
    //             printf("%d ", res[i][j]);
    //         }
    //         printf("\n");
    //     }
    // }
};
// @lc code=end

